The present invention generally relates to a system for transposing a data signal from a first received order to a second different order and, more particularly, concerns a data transposing system which is implemented using a reduced amount of memory.
In many applications, an intelligence bearing signal is encoded, transmitted, and received in the form of plural data blocks each comprising a sequence of individual data elements. Depending on the manner in which the blocks were generated, and depending on their ultimate use in the system, it is frequently necessary to transpose the data elements of each block from the order in which they were received to a different order conforming with their intended use. For example, in a high definition television system, a frame of video data may be divided into a rectangular array of relatively small data blocks to facilitate encoding of the data prior to transmission. Moreover, in order to increase encoding efficiency, it has been found convenient to arrange the data elements in each block in column order. While the video data is thus encoded and transmitted in the form of successive blocks of data elements arranged in columnar order, in the receiver it is desired to provide the data elements in a row scanned format to enable rasterization of the video data for reproducing the televised image. It is thus necessary to transpose the video data from the columnar order in which it is received to a row scanned order appropriate for reproducing the video image.
One well known technique for transposing data from one order to another is the so called ping-pong system. In this system, two memory banks each having a size corresponding to a predetermined number of data blocks are alternately operated on, such that while data is being written into one memory bank, data is simultaneously being read out of the other. By switching appropriately generated write and read address signals between the two memory banks, the data elements may be conveniently reordered in any desired format. While the ping-pong data transposition system is quite flexible, it is extremely wasteful of memory by requiring a memory capable of storing at least two times the number of data elements to be transposed.
Another known data transposition system is represented by the so-called discrete cosine transform (DCT) transposition RAM. The DCT transposition RAM represents a system in which a square array of data elements may be transposed from row to column order by alternately addressing a correspondingly configured memory for writing data elements into memory rows and reading stored data elements from memory columns. While this system requires a memory having a size corresponding only to the number of data elements to be transposed, its use is limited to transposing only square arrays of data elements.